There has been a wide interest in designing distributed algorithms for tinyrobots. In particular, it has been shown that the robots can complete certaintasks even in the presence of faulty robots. In this paper, we focus ongathering of all non-faulty robots at a single point in presence of faultyrobots. We propose a wait-free algorithm (i.e., no robot waits for other robotand algorithm instructs each robot to move in every step, unless it is alreadyat the gathering location), that gathers all non-faulty robots insemi-synchronous model without any agreement in the coordinate system and withweak multiplicity detection (i.e., a robot can only detect that either there isone or more robot at a location) in the presence of at most $n-1$ faulty robotsfor $n\geqslant 3$. We show that the required capability for gathering robotsis minimal in the above model, since relaxing it further makes gatheringimpossible to solve. Also, we introduce an intermediate scheduling model \textit{ASYNC$_{IC}$}between the asynchronous ( i.e., no instantaneous movement or computation) andthe semi-synchronous (i.e., both instantaneous movement and computation) as theasynchronous model with instantaneous computation. Then we propose anotheralgorithm in \textit{ASYNC$_{IC}$} model for gathering all non-faulty robotswith weak multiplicity detection without any agreement on the coordinate systemin the presence of at most $\lfloor n/2\rfloor-2$ faulty robots for $n\geqslant7$.
展开▼
